The invention relates to an error correcting system for correcting errors which occur when reading codewords recorded in a memory apparatus such as a disk drive or the like and, more particularly, to a multibyte error correcting system for correcting errors of a plurality of bytes in a lump by using a Reed-Solomon code.
Hitherto, in a subsystem constructing an external memory apparatus of a computer system, a disk unit as an input/output apparatus is connected under the domination of an input/output controller. According to an error correcting system which is used in such a subsystem, in a lower disk drive, data read out from a memory medium and calculated syndromes are sent to an upper disk controller and are held in a memory and, in the case where a notification of the error detection is received from the disk unit, the correcting operation is executed. Such an error correcting system is known as a deferred type.
On the other hand, there is an error correcting system of the on-the-fly type, in which the operations such that the data read out from the memory medium and the calculated syndromes in the lower disk drive sent to the upper disk controller and held in the memory are not executed, but during the data transfer, namely, while a head is flying over a track (on-the-fly) of the disk, the correcting operation is executed while supplying the data toward the upper input/output control apparatus. According to such an on-the-fly error correcting system, the error correction is performed while transferring the data, without needing the memory storage in the disk controller. Therefore, an exclusive-use time of the disk drive is short and there is no need to break the disk synchronization, so that the next operation can be readily started. After the correctable errors are corrected in the lower disk drive, the error corrected data is sent to the upper input/output control apparatus. In this manner, the advantage, among many, is that the data is handled in substantially the same manner as if there has been no error at all.
In the error correcting system of the desk-top type, whether the upper disk controller can correct the errors or not, the error location, the location of a data subblock having the errors, and the like can be known by the error information from the lower disk drive. In the on-the-fly type error correcting system, since the correctable errors are corrected by the lower disk drive, even if a read error occurs, even a fact that such a read error can be corrected is not known to the upper disk controller. There is, consequently, a problem such that a situation of the error correction cannot be grasped.
In the conventional error correction system, when the errors of the number exceeding the correcting ability occur, there is a possibility such that an erroneous correction or a non-detection occurs. Particularly, in a system for reading and writing user data like a disk drive, so called an unexpected data change occurs and the reliability of the system is remarkably lost.
On the other hand, as one method of correcting the errors by the error correcting system, a chain search method is generally known. The chain search method is particularly effective in the case such as an on-the-fly type for promptly correcting the errors while transferring the data.
That is, according to the chain search, the whole codewords are searched by using an error location polynomial EQU (X.sym..alpha..sup.i1) (X.sym..alpha..sup.i2) (X.sym..alpha..sup.i3) . . . (X.sym..alpha..sup.in)=X.sup.n .sym..beta..sub.n-1 X.sup.n-1 .sym..beta..sub.n-2 X.sup.n-2 .sym. . . . +.beta..sub.1 X.sym..beta..sub.0
and the error location is detected in accordance with whether the value of the above polynomial is zero or non-zero. Coefficients .beta. of this equation are obtained by solving simultaneous equations of (n) unknowns having syndromes as coefficients.
In the error correcting system of the on-the-fly type for quickly correcting the errors, after the syndromes are obtained by reading the codewords, until the data is sent out by setting the system into the error correctable state, only the delay of about one codeword is permitted. Therefore, an arithmetic operating circuit to solve the simultaneous equations of (n) unknowns needs to be realized by a combination circuit. Explaining further in detail, in an input/output unit like a disk drive, a high recording density and a high transfer rate are main targets of the development. To cope with the data read errors due to the high recording density, an error correcting system using a strong code such as a Reed-Solomon code has been put into practical use. In the conventional error correcting system, however, it takes time for processes, and the transfer rate is sacrificed. To solve such a problem, an on-the-fly multibyte error correcting system disclosed in U.S. Pat. No. 4,494,234 is known. According to such a system, however, in order to correct (t) byte errors, a circuit for solving the simultaneous equations of (n) unknowns and for obtaining coefficients .beta..sub.0 to .beta..sub.t-1 of the error location polynomial is necessary. (n) denotes the maximum number of error bytes which can be corrected. (t) is defined as a variable indicative of the number of error bytes which actually occur.
To obtain the simultaneous equations of (n) unknowns having character coefficients, a Cramer's formula is generally used. In this case, it is necessary to develop the simultaneous equations of (n) unknowns to a matrix equation of (n) rows and (n) columns. The number of terms which are obtained after the matrix equation was developed is equal to n!. Therefore, in case of the error correcting ability of n=3 bytes, the number of terms is equal to 6 and a circuit scale also lies within a range in which it can be put into practical use. In case of obtaining the error correcting ability of n=6 bytes, however, the number of terms is equal to 720 and the circuit is also complicated and extremely large.
On the other hand, in the conventional on-the-fly error correcting system, only a subblock of a fixed length is used as a target. A magnetic disk drive to which the error correcting system is applied, however, handles variable length data according to a CKD format. Therefore, a technique regarding how to perform the error correction in the on-the-fly type for the variable length subblock still remains as a subject which is not yet solved.
Each record of the CKD format which is variable-length controlled is divided into subblocks of a fixed length in order to perform the error correction and is set to a variable length by changing the number of subblocks. Further, a length of the last subblock changes in order to match with the user data. In the on-the-fly error correcting system, a delay of one subblock occurs upon error correction. Therefore, as for the last subblock whose length varies, the chain search for the error correction different from that of the other subblocks of the fixed length is needed. Therefore, it is considered to provide arithmetic operating circuits of different chain searches for the error correction of the fixed length subblock and the variable length subblock. With respect to the variable length subblocks, there is a problem such that a different circuit has to be provided with every change in subblock length, and that the circuit scale is too large.
On the other hand, in the record of the CKD format, a header and a counting section are provided at the head of the record and, after that, a plurality of fixed length subblocks follow as a data section. When the header and the counting section are read, the upper controller executes processes which are necessary for the reading and writing operations in a gap provided up to the subsequent subblock. In the on-the-fly error correcting system, however, a delay amount for the error correction is determined to be a delay amount which coincides with the fixed length of the subblock of the data section. Therefore, even with respect to the header and the counting section of the short data length, the error correction result is not obtained unless the same delay as that of the subblock of the data section is applied, so that the processes of the upper controller are delayed by a time corresponding to such a delay. Since the length of gap has to be decided in consideration of the delay time of the error correction, the gap is longer than that in case of the desk-top type error correcting system and there is a problem such that the recording capacity of the disk decreases.